Field of the Invention
The present invention relates to processing of transactions on a distributed processing system, in particular, on a distributed database system and, more specifically, to processing of transactions in a Key Value Store (hereinafter abbreviated as KVS).
Description of Related Art
Distributed database systems are well known and employ conventional techniques. JP2007-188518A relates to distributed database systems that use ownership groups and discloses a step of changing data that indicates ownership of a data item that is an atomic operation.
Distributed database systems generally implement relational databases and use syntaxes such as SQL syntaxes in querying.
More recently, database management software called key value store (KVS) has come into use. This architecture manages maps to store pairs of key and value and allows its application to read a value of a map by specifying the key and write a value of a map with the key. This simple architecture enables low latency for search/update operations and high scalability to increase the performance according to the number of severs. To provide database service with low latency and high throughput, therefore, distributed KVS that can distribute data across multiple servers has been also implemented.
In a simple implementation of KVS, the atomicity and isolation of processes are limited to small processing units. For example, in KVS systems such as memcached and Redis, the atomicity and isolation are guaranteed only for single query/update operation. In WebSphere eXtreme Scale and Google App Engine, the atomicity and isolation are guaranteed only for query/update operations on data managed by only one server. However, when an application performs update operations on data on multiple servers, guaranteeing atomicity and isolation for the operations can be mandatory.
On the other hand, with distributed lock systems, atomicity and isolation for the operations on data managed by multiple servers can be guaranteed, as in conventional distributed databases. However, additional distributed lock systems cause additional complexity for the entire system and lose characteristics of simple implementations of KVS. Specifically, implementing a distributed lock mechanism that covers multiple servers in key value stores with the capabilities of the key value stores is absolutely necessary.
Distributed transactions can be implemented on the KVS by handling each operation of transactions (global transactions) on an application as multiple transactions (local transactions) on the KVS. The transaction is as follows:
First, a state of a lock (ID of a global transaction that holds a lock and the type of the lock), a committed value, and a value being updated are provided as a value of KVS.
A management map is provided on the KVS to manage global transactions. When a global transaction is started, the state of the global transaction is added to the management map as a local transaction.
A query/update process is processed as a local transaction. For each query/update operation in a global transaction, the state of a lock, a committed value, and a value being updated are queried/updated as a local transaction.
A commit/rollback operation in a global transaction is processed as multiple local transactions. The transaction state of the global transaction in the management map is updated as a local transaction, and each queried/updated value of KVS (the state of a lock, a committed value and a value being updated) is also updated as a local transaction.
An example of such an approach is one described in “How to fully use Open-Source: Slim3 on Google App Engine for Java” by Yasuo Higa and Shin-ichi Ogawa, Shuwa System, pp. 241-251. The literature describes how to implement global transactions with Google App Engine.
Also, Google Percolator is described in
http://research.google.com/pubs/pub36726.html.
The existing methods provide a management map on KVS to manage states (Working, Committed and Aborted) of transactions by taking into account an abortion of an application. If the state of a global transaction that is likely to hold a lock for a value is Committed or Aborted, a committed value or a value not updated, respectively, is made available for the other global transactions. However, whenever contention for a lock occurs in such a system, a rollback needs to be performed in order to guarantee isolation.
Google Chubby, described in http://labs.google.com/papers/chubby.html, uses a distributed lock mechanism to enable implementation of distributed transactions. However, building additionally a distributed lock mechanism requires extra software development and management costs.
The present invention eliminates the need for taking into consideration the partitioning of key-value pairs in a simple KVS and therefore increases the versatility of the KVS. In the past, credit transfer applications cannot use a simple KVS in the case where data is divided among multiple servers on a user-ID by user-ID basis. The present invention enables implementation of distributed transactions on KVS without needing to implement an extra distributed lock mechanism.
Moreover, transaction processing for a management map and transaction processing for an application map according to the present invention can increase throughput with an increased number of servers. When lock contention occurs, a transaction is caused to wait for the lock and therefore overhead is low. The present invention has the effect of reducing unintended rollbacks by maintaining an exclusive lock of a management map during a transaction.